Ghi chú NP-đầy_đủ

  1. ↑ Cook, S.A. (1971). “The complexity of theorem proving procedures”. Proceedings, Third Annual ACM Symposium on the Theory of Computing, ACM, New York. tr. 151–158. doi:10.1145/800157.805047. 
  2. ↑ Richard M. Karp (1972). “Reducibility Among Combinatorial Problems”. Trong R. E. Miller and J. W. Thatcher (editors). Complexity of Computer Computations. New York: Plenum. tr. 85–103. 
  3. ↑ Garey, M.R.; Johnson, D.S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W.H. Freeman. ISBN 0-7167-1045-5.  Chú thích sử dụng tham số |coauthors= bị phản đối (trợ giúp)
Các lớp độ phức tạp quan trọng (thêm)
Các lớp được coi là giải được
DLOGTIME • AC0 • ACC0 • TC0 • L • SL • RL • NL • NC • SC • P (P-đầy đủ) • ZPP • RP • BPP • BQP 
Các lớp có thể không giải được
Các lớp được coi là không giải được
EXPTIME • NEXPTIME • EXPSPACE • ELEMENTARY • PR • R • RE • ALL
Các hệ thống cấp bậc
Các nhóm các lớp độ phức tạp